import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-07
 * Time: 22:48
 */
public class Solution {
//    堆
//    将所有结果放到大小为 k 的大根堆里面
//    最后堆顶元素就是结果
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int[] ans = new int[2];
        int len = arr.length;
        // 注意使用的是大根堆
        PriorityQueue<double[]> maxHeap = new PriorityQueue<>((o1, o2) -> Double.compare(o2[0], o1[0]));
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                double val = arr[i]*1.0/arr[j];
                if (maxHeap.size() < k) {
                    maxHeap.offer(new double[]{val, arr[i], arr[j]});
                } else {
                    // 比堆顶元素小就弹出堆顶, 将该元素放进去
                    if (maxHeap.peek()[0] > val) {
                        maxHeap.poll();
                        maxHeap.offer(new double[]{val, arr[i], arr[j]});
                    }
                }
            }
        }
        double[] array = maxHeap.peek();
        ans[0] = (int)array[1];
        ans[1] = (int)array[2];
        return ans;
    }

//     方法二: 优先级队列 + 多路归并
//     选定 j 之后, 那么 arr[i]/arr[j],  (i=0.1.2.3...< j) 一定是递增的
//     所以一共有多路递增序列, 使用优先级队列进行多路归并
//     弹出 k-1 个最小值之后堆顶就是结果
//     注意因为每路长度不一致,所以注意有的路先结束, 先结束的路就不用再管了
    public int[] kthSmallestPrimeFraction2(int[] arr, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingDouble(a -> arr[a[0]] * 1.0 / arr[a[1]]));
        int len = arr.length;
        for (int j = 1; j < len; j++) {
            minHeap.offer(new int[]{0, j});
        }
        // 从 堆中弹出 k - 1 个, 最后堆顶元素就是结果的下标
        for (int i = 1; i < k; i++) {
            int[] top = minHeap.poll();
            if (top[0] + 1 != top[1]) {
                // 这一路还没有归并完
                minHeap.offer(new int[]{top[0]+1, top[1]});
            }
        }
        // 堆顶就是结果的下标
        int[] top = minHeap.poll();
        return new int[]{arr[top[0]], arr[top[1]]};
    }



    int a;
    int b;
    double PRECISE = 0.00000001;

    // 方法三: 双指针 + 二分
    public int[] kthSmallestPrimeFraction3(int[] arr, int k) {
        double left = 0;
        double right = 1;
        // 最后值的范围一定是 [0, 1]
        // 把 [0, 1] 进行二分
        // 查找 x 使得 <= x 的有 k 个
        // 那么最接近 x 的那一对 arr[i], arr[j] 就是结果

        // 为什么二分的条件是 right - left > PRECISE
        // 而不是 left < right ?
        // 因为 它们的类型都是 double , 那么 mid 不可能等于它们其中一个
        // 而后面都是 根据 mid 对 left right 进行赋值的, 所以 left 和 right 不可能相等
        while (right - left > PRECISE ) {
            double mid = (left + right) / 2;
            int n = count(arr, mid);
            if (n == k) {
                return new int[]{a, b}; // 等于 k 可以直接返回, 因为 题目说了, 不可能有相同的值
            }
            if (n < k) {
                left = mid; // 为什么 left 和 right 都可以赋值为 mid, 因为 mid 不可能等于 left 和 right 中的任一个
            } else {
                right = mid;
            }
        }
        return null;
    }

    public int count(int[] arr, double val) {
        // 每次重新计数都要设置 a = 0, b = 1
        // 因为我们要找的是 < val 但最接近 val 的一对
        // 所以我们要找的是最大值, 但是其他计数时 结果 > k 个了这些结果都不能算
        // 所以要每次计数时重新赋值
        a = 0;
        b = 1;
        int len = arr.length;
        int ans = 0;
        for (int i = 0, j = 1; j < len; j++) {
            // 确定 j 之后, i 是随着 j 增大的, 所以时间复杂度为 O(N)
            while (arr[i+1]*1.0/arr[j] <= val) {
                // 使用 i+1 是为了能够记录最后一个满足条件的值
                i++;
            }
            if (arr[i]*1.0/arr[j] <= val) {
                ans += (i+1);
                // 记录接近 val 的最大值
                // 注意这个要放到外层的判断里面, 因为可能这一路第一个就 > val
                if (arr[i]*b > arr[j]*a) {
                    a = arr[i];
                    b = arr[j];
                }
            }

        }
        return ans;
    }
}
